package com.leetcode.sort;

/**
 * leetcode 75 颜色的分类
 */
public class Solution75 {
    public void sortColors(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }

        sortColors(nums, 0, nums.length - 1);
    }

    private void sortColors(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }

        int partition = nums[start];
        int index = start + 1;
        int left = start;
        int right = end;
        while (index <= right) {
            if (nums[index] < partition) {
                swap(nums, left++, index++);
            } else if (nums[index] > partition) {
                swap(nums, right--, index);
            } else {
                index++;
            }
        }
        sortColors(nums, start, left - 1);
        sortColors(nums, right + 1, end);
    }

    private void swap(int[] nums, int index1, int index2) {
        int tmp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = tmp;
    }
}
